/* ***** BEGIN LICENSE BLOCK *****
 *   Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 * 
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Save File to.
 *
 * The Initial Developer of the Original Code is
 * Atte Kemppilä.
 * Portions created by the Initial Developer are Copyright (C) 2007
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 * 
 * ***** END LICENSE BLOCK ***** */


var EXPORTED_SYMBOLS =
[
    "Heap"
];


/*
 * Heap algorithm is taken from:
 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
 */

function Heap(compare)
{
    this.heap = [];
    this.compare = (compare ? compare : this._compare);
}

Heap.prototype =
{
    get length() { return this.heap.length; },
    
    push: function Heap_push(value)
    {
        var heap = this.heap;
        var compare = this.compare;
        var index = heap.length + 1;
        var parent = index >> 1;
        
        while ((parent > 0) && (compare(value, heap[parent - 1]) > 0))
        {
            heap[index - 1] = heap[parent - 1];
            index = parent;
            parent = parent >> 1;
        }
        
        heap[index - 1] = value;
    },
    
    peek: function Heap_peek()
    {
        var heap = this.heap;
        var length = heap.length;
        
        if (length == 0)
            throw new Error("heap is empty");
        
        return heap[0];
    },
    
    pop: function Heap_pop()
    {
        var heap = this.heap;
        var length = heap.length;
        
        if (length == 0)
            throw new Error("heap is empty");
        
        var value = heap[0];
        heap[0] = heap[length - 1];
        heap.length = length - 1;
        this._heapify(1);
        
        return value;
    },
    
    _heapify: function Heap__heapify(index)
    {
        var heap = this.heap;
        var compare = this.compare;
        var length = heap.length;
        var left = index * 2;
        var right = index * 2 + 1;
        var max = index;
        
        if ((left <= length) && (compare(heap[left - 1], heap[max - 1]) > 0))
            max = left;
        if ((right <= length) && (compare(heap[right - 1], heap[max - 1]) > 0))
            max = right;
        
        if (max != index)
        {
            [heap[index - 1], heap[max - 1]] = [heap[max - 1], heap[index - 1]];
            this._heapify(max);
        }
    },
    
    _compare: function Heap__compare(a, b)
    {
        return ((a < b) ? -1 : ((a == b) ? 0 : 1));
    }
}
